package myutil.mymap;

import java.util.Iterator;

/**
 *
 * @author Hlib_Babii
 */
public class MyHashMap<K, V> implements MyMap<K, V> {

    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    private static final int MAX_CAPACITY = 1 << 30;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private float loadFactor;
    /**
     * the number of entries in this map
     */
    private int size;
    /**
     * the size of this map must not exceed this value
     */
    private int threshold;
    /**
     *
     */
    private SimpleEntry<K, V>[] buckets;

    /**
     * constructs an empty HashMap with the default initial capacity (16) and
     * the default load factor (0.75).
     */
    public MyHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /**
     * constructs an empty HashMap with the specified initial capacity and the
     * default load factor (0.75).
     *
     * @param initialCapacity initial capacity
     */
    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * constructs an empty HashMap with the specified initial capacity and load
     * factor.
     *
     * @param initialCapacity initial capacity
     * @param loadFactor load factor
     */
    public MyHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity <= 0 || initialCapacity > MAX_CAPACITY) {
            initialCapacity = DEFAULT_INITIAL_CAPACITY;
        }
        if (!(loadFactor <= 0.0)) {
            loadFactor = DEFAULT_LOAD_FACTOR;
        }
        this.loadFactor = loadFactor;
        threshold = (int) Math.min(initialCapacity * loadFactor, MAX_CAPACITY);
        buckets = new SimpleEntry[initialCapacity];
    }

    public static class SimpleEntry<K, V> implements Entry<K, V> {

        private final K key;
        private V value;
        private SimpleEntry<K, V> next;

        SimpleEntry(K key, V value, SimpleEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            final V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
    }

    /**
     * removes all the entries from the map
     */
    @Override
    public void clear() {
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = null;
        }
        this.size = 0;
    }

    /**
     * checks if this map contains entry with specified key
     *
     * @param key key which existence is checked
     * @return returns true if there is entry with specified key, false
     * otherwise
     */
    @Override
    public boolean containsKey(K key) {
        return getEntry(key) != null;
    }

    /**
     * checks if this map contains entry with specified value
     *
     * @param value key which existence is checked
     * @return returns true if there is entry with specified value, false
     * otherwise
     */
    @Override
    public boolean containsValue(V value) {
        for (SimpleEntry<K, V> bucket : buckets) {
            for (SimpleEntry<K, V> entry = bucket; entry != null; entry = entry.next) {
                V curValue = entry.getValue();
                if ((value == null && curValue == null)
                        || (value != null && curValue.equals(value))) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Returns the value to which the specified key is mapped, or {@code null}
     * if this map contains no mapping for the key. A return value of
     * {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also possible
     * that the map explicitly maps the key to {@code null}. The
     * {@link #containsKey containsKey} operation may be used to distinguish
     * these two cases
     *
     * @param key key mapping for which is to be retrieved
     * @return the value to which the specified key is mapped, or {@code null}
     * if this map contains no mapping for the key.
     */
    @Override
    public V get(K key) {
        final SimpleEntry<K, V> entry = getEntry(key);
        return entry == null ? null : entry.getValue();
    }

    /**
     * checks if this map contains any entries
     *
     * @return false if this map contains any entries, true otherwise
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Maps specified value to specified key and returns the previous mapping of
     * this key if there was one, null otherwise. Null can be both key and
     * value.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with {@code key}, or {@code null}
     * if there was no mapping for {@code key}. (A {@code null} return can also
     * indicate that the map previously associated {@code null} with
     * {@code key}.)
     */
    @Override
    public V put(K key, V value) {
        if (size >= threshold) {
            addBucketsAndRehash(buckets.length * 2);
        }
        final SimpleEntry<K, V> entry;
        if (key == null) {
            entry = getNullEntry();
            if (entry == null) {
                addNullEntry(value);
                return null;
            }
        } else {
            int bucket = getBucketNumber(key);
            entry = getEntry(bucket, key);
            if (entry == null) {
                addEntry(bucket, key, value);
                return null;
            }
        }
        V toReturn = entry.getValue();
        entry.setValue(value);
        return toReturn;
    }

    /**
     * Removes and returns mapping for the specified key if there is one.
     *
     * @param key key mapping for which is to be deleted.
     * @return mapping for the specified key if there is one, null otherwise
     */
    @Override
    public V remove(K key) {
        final Entry<K, V> entry;
        if (key == null) {
            entry = removeNullEntry();
        } else {
            int bucket = getBucketNumber(key);
            entry = removeEntry(bucket, key);
        }
        return entry == null ? null : entry.getValue();
    }

    /**
     * Returns the number of entries in this map
     *
     * @return the number of entries in this map
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Returns the iterator that iterates over the entries
     *
     * @return the iterator that iterates over the entries
     */
    @Override
    public Iterator entryIterator() {
        return new EntryIterator();
    }

    /**
     * gets entry from the specified bucket with the specified key
     *
     * @param bucket
     * @param key
     * @return entry from the specified bucket with the specified key
     */
    private SimpleEntry<K, V> getEntry(int bucket, K key) {
        for (SimpleEntry<K, V> entry = buckets[bucket];
                entry != null; entry = entry.next) {
            if (entry.key.equals(key)) {
                return entry;
            }
        }
        return null;
    }

    /**
     * returns hash for the specified key
     *
     * @param key key to get hash for
     * @return hash for the specified key
     */
    private int getHash(K key) {
        return key.hashCode();
    }

    /**
     * Returns a number of the bucket where the specified key is stored
     *
     * @param key key for which a number of the bucket to be found
     * @return a number of the bucket where the specified key is stored
     */
    private int getBucketNumber(K key) {
        int keyHash = getHash(key);
        return keyHash & (buckets.length - 1);
    }

    /**
     * Creates a new bucket array that consists {@code numberOfBuckets} elements
     *
     * @param newNumberOfBuckets ASSUME IS A POWER OF 2
     */
    private void addBucketsAndRehash(int newNumberOfBuckets) {
        if (newNumberOfBuckets > MAX_CAPACITY) {
            newNumberOfBuckets = MAX_CAPACITY;
            threshold = MAX_CAPACITY;
        } else {
            threshold = (int) (newNumberOfBuckets * loadFactor);
        }

        SimpleEntry[] oldBuckets = buckets;
        buckets = new SimpleEntry[newNumberOfBuckets];
        size = 0;
        for (SimpleEntry oldBucket : oldBuckets) {
            for (SimpleEntry<K, V> entry = oldBucket; entry != null; entry = entry.next) {
                int bucket = getBucketNumber(entry.getKey());
                addEntry(bucket, entry.getKey(), entry.getValue());
            }
        }
    }

    /**
     * return entry for the specified key
     *
     * @param key
     * @return entry for the specified key
     */
    private SimpleEntry<K, V> getEntry(K key) {
        final SimpleEntry<K, V> entry;
        if (key == null) {
            entry = getNullEntry();
        } else {
            int bucket = getBucketNumber(key);
            entry = getEntry(bucket, key);
        }
        return entry;
    }

    private SimpleEntry<K, V> removeEntry(int bucket, K key) {
        if (buckets[bucket] != null) {
            if (buckets[bucket].getKey().equals(key)) {
                final SimpleEntry<K, V> toRemove = buckets[bucket];
                buckets[bucket] = buckets[bucket].next;
                --size;
                return toRemove;
            }
            for (SimpleEntry<K, V> entry = buckets[bucket];
                    entry.next != null; entry = entry.next) {
                if (entry.next.getKey().equals(key)) {
                    final SimpleEntry<K, V> toRemove = entry.next;
                    entry.next = toRemove.next;
                    --size;
                    return toRemove;
                }
            }
        }
        return null;
    }

    private void addEntry(int bucket, K key, V value) {
        buckets[bucket] = new SimpleEntry<>(
                key, value, buckets[bucket]);
        ++size;
    }

    // logic for putting, getting and removing entries with null-keys is separated
    // as it is a special case
    private SimpleEntry<K, V> getNullEntry() {
        for (SimpleEntry<K, V> entry = buckets[0]; entry != null; entry = entry.next) {
            if (entry.getKey() == null) {
                return entry;
            }
        }
        return null;
    }

    private SimpleEntry<K, V> removeNullEntry() {
        if (buckets[0] != null) {
            if (buckets[0].getKey() == null) {
                final SimpleEntry<K, V> entry = buckets[0];
                buckets[0] = buckets[0].next;
                --size;
                return entry;
            }
            for (SimpleEntry<K, V> entry = buckets[0]; entry.next != null;
                    entry = entry.next) {
                if (entry.next.getKey() == null) {
                    final SimpleEntry<K, V> toRemove = entry.next;
                    entry.next = toRemove.next;
                    --size;
                    return toRemove;
                }
            }
        }

        return null;
    }

    private void addNullEntry(V value) {
        buckets[0] = new SimpleEntry<>(null, value, buckets[0]);
        ++size;
    }

    class EntryIterator implements Iterator<SimpleEntry<K, V>> {

        /**
         * bucket where element referenced by {@code next} stored
         */
        private int nextBucket = 0;
        
        /**
         * bucket where element referenced by {@code lastReturned} stored
         */
        private int lastReturnedBucket = 0;
        
        private SimpleEntry<K, V> lastReturned = null;
        private SimpleEntry<K, V> next = buckets[0];

        public EntryIterator() {
            skipNullBuckets();
        }

        @SuppressWarnings("empty-statement")
        private void skipNullBuckets() {
            if (next == null) {
                ++nextBucket;
                while (nextBucket < buckets.length
                        && buckets[nextBucket] == null) {
                    nextBucket++;
                }
                next = (nextBucket < buckets.length) ? buckets[nextBucket]
                        : null;
            }
        }

        @Override
        public boolean hasNext() {
            return (next != null);
        }

        @Override
        public SimpleEntry<K, V> next() {
            if (next != null) {
                lastReturned = next;
                next = lastReturned.next;
                lastReturnedBucket = nextBucket;
                skipNullBuckets();
            } else {
                lastReturned = null;
            }
            return lastReturned;
        }

        @Override
        public void remove() {
            // it's more efficient to search for
            // entry that preceeds one we have to remove from the beginning
            // of the list then to store Entry<K, V> beforeLastReturned 
            // and reassign it every time
            if (lastReturned == null) {
                return;
            }
            if (buckets[lastReturnedBucket] == lastReturned) {
                buckets[lastReturnedBucket] = lastReturned.next;
            } else {
                SimpleEntry<K, V> entry;
                for (entry = buckets[lastReturnedBucket];
                        entry.next != lastReturned; entry = entry.next) {}
                entry.next = lastReturned.next;
            }
            --size;
            lastReturned = null;
        }
    }
}
